摘要 :
In this paper we investigate reachability relations on the vertices of digraphs. IfW is a walk in a digraph D, then the height of W is equal to the number of edgestraversed in the direction coinciding with their orientation, minus...
展开
In this paper we investigate reachability relations on the vertices of digraphs. IfW is a walk in a digraph D, then the height of W is equal to the number of edgestraversed in the direction coinciding with their orientation, minus the number ofedges traversed opposite to their orientation. Two vertices u, v E V(D) are Ra,b-related if there exists a walk of height 0 between u and v such that the height ofevery subwalk of W, starting at u, is contained in the interval [a, b], where a is anon-positive integer or a = and b is a non-negative integer or b = no. Of coursethe relations Ra,b are equivalence relations on V (D). Factorising digraphs by Ra,and R,b, respectively, we can only obtain a few different digraphs. Dependingupon these factor graphs with respect to R,b and Ra, it is possible to definefive different "basic relation-properties for R,b and Ra,, respectively. Besides proving general properties of the relations Ra,b, we investigate the ques-tion which of the "basic relation-properties" with respect to R,b and Ra, canoccur simultaneously in locally finite connected transitive digraphs. Furthermorewe investigate these properties for some particular subclasses of locally finite con-nected transitive digraphs such as Cayley digraphs, digraphs with one, with two orwith infinitely many ends, digraphs containing or not containing certain directedsubtrees, and highly arc transitive digraphs.
收起
摘要 :
In this paper we study reachability relations on vertices of digraphs, informally defined as follows. First, the weight of a walk is equal to the number of edges traversed in the direction coinciding with their orientation, minus ...
展开
In this paper we study reachability relations on vertices of digraphs, informally defined as follows. First, the weight of a walk is equal to the number of edges traversed in the direction coinciding with their orientation, minus the number of edges traversed in the direction opposite to their orientation. Then, a vertex u is -related to a vertex v if there exists a 0-weighted walk from u to v whose every subwalk starting at u has weight in the interval [0,k]. Similarly, a vertex u is -related to a vertex v if there exists a 0-weighted walk from u to v whose every subwalk starting at u has weight in the interval [-k,0]. For all positive integers k, the relations and are equivalence relations on the vertex set of a given digraph.
收起
摘要 :
In A. Malni?, D. Maru?i?, N. Seifter, P. ?parl and B. Zgrabli?, Reachability relations in digraphs, Europ. J. Combin. 29?(2008), 1566–1581,?it was shown that properties of digraphs such as growth, property Z, and number of ends a...
展开
In A. Malni?, D. Maru?i?, N. Seifter, P. ?parl and B. Zgrabli?, Reachability relations in digraphs, Europ. J. Combin. 29?(2008), 1566–1581,?it was shown that properties of digraphs such as growth, property Z, and number of ends are reflected by the properties of certain reachability relations defined on the vertices of the corresponding digraphs.In this paper we study these relations in connection with certain properties of automorphism groups of transitive digraphs. In particular, one of the main results shows that if a transitive digraph admits a nilpotent subgroup of automorphisms with finitely many orbits, then its nilpotency class and the number of orbits are closely related to particular properties of reachability relations defined on the digraphs in question.The obtained results have interesting implications for Cayley digraphs of certain types of groups such as torsion-free groups of polynomial growth.
收起
摘要 :
Let D be a locally finite, connected, 1-arc transitive digraph. It is shown that the reachability relation is not universal in D provided that the stabilizer of an edge satisfies certain conditions which seem to be typical for hig...
展开
Let D be a locally finite, connected, 1-arc transitive digraph. It is shown that the reachability relation is not universal in D provided that the stabilizer of an edge satisfies certain conditions which seem to be typical for highly arc transitive digraphs. As an implication, the reachability relation cannot be universal in highly arc transitive digraphs with prime in- or out-degree. Two different aspects of the connection between highly arc transitive digraphs and the theory of totally disconnected locally compact groups are also considered.
收起
摘要 :
We present results on the structure of graphs with polynomial growth. For certain classes of these graphs we prove that they contain subgraphs which are similar to the lattice graph L~d. These results are then applied to investiga...
展开
We present results on the structure of graphs with polynomial growth. For certain classes of these graphs we prove that they contain subgraphs which are similar to the lattice graph L~d. These results are then applied to investigate isoperimetric properties of certain classes of graphs with polynomial growth. In addition, these structural results can also be applied to percolation problems.
收起
摘要 :
In an infinite digraph D, an edge e' is reachable from an edge e if there exists an alternating walk in D whose initial and terminal edges are e and e'. Reachability is an equivalence relation and if D is 1-arc-transitive, then th...
展开
In an infinite digraph D, an edge e' is reachable from an edge e if there exists an alternating walk in D whose initial and terminal edges are e and e'. Reachability is an equivalence relation and if D is 1-arc-transitive, then this relation is either universal or all of its equivalence classes induce isomorphic bipartite digraphs. In Combinatorica, 13 (1993), Cameron, Praeger and Wormald asked if there exist highly arc-transitive digraphs (apart from directed cycles) for which the reachability relation is not universal and which do not have a homomorphism onto the two-way infinite directed path (a Cayley digraph of Z with respect to one generator). In view of an earlier result of Praeger in Australas. J. Combin., 3 (1991), such digraphs are either locally infinite or have equal in- and out-degree. In European J. Combin., 18 (1997), Evans gave an affirmative answer by constructing a locally infinite example.
收起
摘要 :
In this paper we investigate infinite, locally finite, connected, transitive digraphs with more than one end. For undirected graphs with these properties it has been shown that they are trees as soon as they are 2-arc transitive. ...
展开
In this paper we investigate infinite, locally finite, connected, transitive digraphs with more than one end. For undirected graphs with these properties it has been shown that they are trees as soon as they are 2-arc transitive. In the case of digraphs the situation is much more involved. We show that these graphs can have both thick and thin ends, even if they are highly arc transitive. Hence they are far away from being ‘tree-like’. On the other hand all known examples of digraphs with more than one end are either highly arc transitive or at most 1-arc transitive. We conjecture that infinite, locally finite, connected, 2-arc transitive digraphs with more than one end are highly arc transitive and prove that this conjecture holds for digraphs with prime in- and out-degree and connected cuts.
收起
摘要 :
Let G be a finite connected simple graph with n vertices. We show a close relation between the domination number γ(G) and the largest eigenvalue λ_n of the Laplacian matrix of G. If γ(G) ≥ 3, then λ_n < n - [(γ(G)-2)/2] . If γ(G) = 1, then λ_n = n. If γ(G) = 2, no better bound than λ_n ≤ n exists. Furthermore we show that eigenvectors corresponding to large eigenvalues induce dominating sets in G....
展开
Let G be a finite connected simple graph with n vertices. We show a close relation between the domination number γ(G) and the largest eigenvalue λ_n of the Laplacian matrix of G. If γ(G) ≥ 3, then λ_n < n - [(γ(G)-2)/2] . If γ(G) = 1, then λ_n = n. If γ(G) = 2, no better bound than λ_n ≤ n exists. Furthermore we show that eigenvectors corresponding to large eigenvalues induce dominating sets in G.
收起
原文获取